package Aleehot100;

/**
 * ClassName: c087
 * Package: Aleehot100
 * Description:300. 最长递增子序列
 *
 * @Author BCXJ
 * @Create 2025/9/10 09:02
 * @Version 1.0
 * @Since 1.0
 */
public class c087 {
    public static void main(String[] args) {
        int[] arr = {10,9,2,5,3,7,101,18};
        System.out.println(lengthOfLIS(arr));
    }


    public static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if(0 == n) {
            return 0;
        }
        //维护一个tail数组，tail[i]表示长度为i+1的递增子序列的最小末尾值。
        int[] tail = new int[n];
        int len = 0; // 表示有序tail的长度
        tail[len ++] = nums[0];

        for (int i = 1; i < n; i++) {
            if(nums[i] > tail[len - 1]) {
                tail[len ++] = nums[i];
            } else {
                // 二分查找
                int left = 0, right = len - 1, mid = 0;
                // 找出>= num[i] 的最左边的位置
                while(left < right) {
                    mid = left + ((right - left) >> 1);
                    if(tail[mid] < nums[i]) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                tail[left] = nums[i];
            }
        }
        return len;
    }


}
